#2021年省赛-填空题 回路计数
import math
n = 21
state = 1 << 21  # 状态压缩，用21位二进制表示访问状态（2^21种状态）
# 存放教学楼之间是否有路径
# Map尺寸是 22*22 是为了让数组索引与教学楼编号一一对应
Map = [[0] * (n + 1) for _ in range(n + 1)]
dp = [[0] * n for _ in range(state)]
dp[1][0] = 1  # 只访问1号楼

for i in range(n + 1):
    for j in range(n + 1):
        if math.gcd(i, j) == 1:  # 楼号互质则有路径
            Map[i][j] = 1

for i in range(state):  # 遍历所有可能的状态i（从0到2^21-1）
    for j in range(n):  # 遍历所有可能的终点楼号j（0到20）
        if i >> j & 1:  # j这栋楼是不是访问过
            for k in range(n):  # 遍历所有可能的前一个楼号k（0到20）
                if Map[k + 1][j + 1] == 1 and i >> k & 1:  # k到j有路径且k在状态i中
                    # 状态转移方程
                    dp[i][j] += dp[i - (1 << j)][k]
                    #print(f"i={i}, j={j}, k={k}, dp[i][j]={dp[i][j]}")
# 计算所有楼都被访问过的总路径数
# 减去以1号楼为终点的回路数
# 输出不构成回路的路径数
print(dp[-1][0])
# dp[-1][0] 是以1号楼为终点的路径数（即回路数）